//
// Created by daiyizheng on 2022/4/12.
//
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    //dfs+记忆化搜索
    int dfs(vector<int>& nums, int i, vector<int>& memo){
        if (i>=nums.size()){return 0;}

        if(memo[i]!=-1)return memo[i];

        int left  =dfs(nums, i+1, memo);
        int right = dfs(nums, i+2, memo);

        memo[i] = max(left, right+nums[i]);

        return memo[i];

    }
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n==0)return 0;

        vector<int> memo(n,-1);
        return dfs(nums, 0, memo);
    }

    //动态规划
    int rob1(vector<int>& nums) {
        int n = nums.size();
        if (n==0)return 0;
        vector<int> dp(n+1);
        //初始化
        dp[0] = 0;
        dp[1] = nums[0];

        for (int i = 2; i <=n ; ++i) {
            dp[i] = max(dp[i-1], dp[i-2]+nums[i-1]);
        }
        return dp[n];
    }

    //动态规划
    int rob2(vector<int>& nums) {
        int n = nums.size();
        if (n<=1)return nums[0];
        vector<int> dp(n);
        //初始化
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i <n ; ++i) {
            dp[i] = max(dp[i-1], dp[i-2]+nums[i]);
        }
        return dp[n-1];
    }
};